#include<stdio.h>
#include<stdlib.h>
#include<algorithm>

typedef struct BiThrNode
{				
	char data;					
	struct BiThrNode *lchild,*rchild;	
	int LTag,RTag;
}BiThrNode,*BiThrTree;


BiThrNode *pre =new BiThrNode;


void CreateBiTree(BiThrTree &T)
{	
	char ch;
	scanf("%c",&ch);
	if(ch=='#')  T=NULL;			
	else
	{	
        T = new BiThrNode;						
		T->data=ch;					
		CreateBiTree(T->lchild);	
		CreateBiTree(T->rchild);	
	}								
}									

void InThreading(BiThrTree p)
{
	if(p)
	{
		InThreading(p->lchild);             			
		if(!p->lchild)
		{                   							
			p->LTag=1;                                 
			p->lchild=pre; 								
		} 
		else
			p->LTag=0;
		if(!pre->rchild)
		{												
			pre->RTag=1;                   				
			pre->rchild=p;                     			
		}
		else
			pre->RTag=0;
		pre=p;                       					
		InThreading(p->rchild);               			
    }
}//InThreading
//查找后继
BiThrNode *inorderNext(BiThrNode *pointer)
{
    if (pointer->RTag==1){
        return pointer->rchild;
        }    
    else {    
        pre=pre->rchild; /* 找右子树最先访问的结点 */
        while(pre->LTag==0)
            pre=pre->lchild;      
        return pre;
     }
}
//找到x结点
void findnext(BiThrNode *p,char x){
   BiThrNode *t;
   BiThrNode *ans;
   t=p->lchild;
    while (t!=p)
    {   
        if(t->data==x) ans=t;
        while(t->LTag==0){
            t=t->lchild;
            if(t->data==x) ans=t;
        }
        printf("%c ",t->data);    
        if(t->data==x) ans=t;
        while(t->RTag==1&&t->rchild!=p){
            t=t->rchild;
            printf("%c ",t->data);
            if(t->data==x) ans=t;
        }
        t=t->rchild;
    }
    printf("\n需要找后继结点的是:%c",ans->data);
    ans=inorderNext(ans);
    printf("\n结点%c的后继结点是:%c",x,ans->data);
}
//插入一个结点p 使其成为s结点的右孩子
void InOrderThreading (BiThrTree &Thrt,BiThrTree T)
{
	//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点
	Thrt=new BiThrNode;          		//建头结点
	Thrt->LTag=0;                 		//头结点有左孩子，若树非空，则其左孩子为树根
	Thrt->RTag=1;               		//头结点的右孩子指针为右线索
	Thrt->rchild=Thrt;            		//初始化时右指针指向自己
	if(!T)  Thrt->lchild=Thrt;      	//若树为空，则左指针也指向自己
	else
	{
	  Thrt->lchild=T;  pre=Thrt; 	 	//头结点的左孩子指向根，pre初值指向头结点
	  InThreading(T);              		//调用算法5.7，对以T为根的二叉树进行中序线索化
	  pre->rchild=Thrt;          	  	//算法5.7结束后，pre为最右结点，pre的右线索指向头结点
	  pre->RTag=1;  	             
	  Thrt->rchild=pre;             	//头结点的右线索指向pre
	}
} 		
int main()
{
	BiThrTree tree,tree_x,ans;
	printf("输入先序序列：\n");
	CreateBiTree(tree);
    pre->RTag=1;
	pre->rchild=NULL;
	// InThreading(tree);
    InOrderThreading(tree_x,tree);
	printf("线索化完毕\n");
    // ans = findnext(tree_x,'c');
    // printf("%c",ans->data);
    findnext(tree_x,'b');
    return 0;
}
//先序序列 -+a##*b##-c##d##/e##f###
//先序序列 abc##de#g##f###